class Solution(object):
    def findBall(self, grid):
        m = len(grid)
        n = len(grid[0])
        ans = [-1] * n

        def dfs(i, j, state):
            if j < 0 or j >= n:
                return -1
            if i == m:
                return j
            if state == 0:
                if grid[i][j] == 1:
                    return dfs(i, j + 1, 1)
                if grid[i][j] == -1:
                    return dfs(i, j - 1, 2)
            if state == 1:
                if grid[i][j] == 1:
                    return dfs(i + 1, j, 0)
                if grid[i][j] == -1:
                    return - 1
            if state == 2:
                if grid[i][j] == 1:
                    return - 1
                if grid[i][j] == -1:
                    return dfs(i + 1, j, 0)

        for j in range(n):
            ans[j] = dfs(0, j, 0)

        return ans